# 最长连续序列（Longest Consecutive Sequence） 是指由连续整数组成的最长子序列，该子序列中的元素可以不连续出现于原数组中，
# 但必须严格递增且相邻元素之间的差值为 1。因此要用set对原数据进行去重
from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        longest = 0
        for x in nums_set:
            # x - 1不在，说明x是开头的
            if (x - 1) not in nums_set:
                #易错点：不要忘记把第一个计数
                length = 1
                while (x + 1) in nums_set:
                    length += 1
                    x += 1
                longest = max(length, longest)

        return longest


#注意，第一思路往往会想到如下思想，但是因为快排的引入，其计算复杂度是olog（n），所以不符合题目要求
#!!!以下为错误解法！！！

    # def longestConsecutive(self,nums: List[int]) -> int:
    #     if not nums:
    #         return 0
    #     nums.sort()
    #     ans = 0
    #     tmp = 1
    #     for i in range(1, len(nums)):
    #         if nums[i] == nums[i - 1]:
    #             continue  # 跳过相同的元素
    #         elif nums[i] == nums[i - 1] + 1:
    #             tmp += 1   # 连续
    #         else:
    #             ans = max(ans, tmp)  # 中断，结算
    #             tmp = 1
    #     return max(ans, tmp)


#输入格式1：100 4 200 1 3 2
nums = [100, 4, 200, 1, 3, 2]
#预期输出：4
solution = Solution()
print(solution.longestConsecutive(nums))


nums = [0,3,7,2,5,8,4,6,0,1]
#预期输出：9

solution = Solution()
print(solution.longestConsecutive(nums))
